package com.seven.leetcode.problems;

import com.seven.leetcode.utils.ListNode;

import java.util.Arrays;

/**
 * 21. 合并两个有序链表
 * MergeTwoSortedLinkedLists
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 级别：Easy
 * <p>
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * <p>
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * <p>
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *
 * @author : wenguang
 * @date : 2021/3/22 9:26
 */
public class MergeTwoSortedLinkedLists {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 4};
        ListNode node1 = ListNode.fromArray(nums1);
        int[] nums2 = new int[]{1, 3, 4};
        ListNode node2 = ListNode.fromArray(nums2);
        System.out.println("in: \nnums1" + Arrays.toString(nums1) + "\nnums2: " + Arrays.toString(nums2));
        ListNode result = mergeTwoLists(node1, node2);
        System.out.println("out: " + result);
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (null == l1) {
            return l2;
        }
        if (null == l2) {
            return l1;
        }

        ListNode node = new ListNode();
        ListNode head = node;

        while (null != l1 && null != l2) {
            if (l1.val <= l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }

            node = node.next;
        }

        if (null != l1) {
            node.next = l1;
        }

        if (null != l2) {
            node.next = l2;
        }

        return head.next;
    }
}
